package com.celan.year2023.month05.day28;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Celan
 * @description TODO
 */
public class Solution03 {
    public boolean isValidSerialization(String preorder) {
        String[] preorders = preorder.split(",");
        int n = preorders.length;
        if (n == 1 && preorders[0].charAt(0) == '#') return true;

        //根节点不能为空
        if (preorders[0].charAt(0) == '#') return false;
        Stack<Integer> stack = new Stack<>();
        //将第一个字母读入并入栈
        stack.push(2);

        for (int i = 1; i < n; i++) {
            char c = preorders[i].charAt(0);
            //若还没有结束栈已空,说明无法正常序列化
            if (stack.isEmpty()) return false;

            if (c == '#') {
                //当遇到空节点时,仅将栈顶元素减 1
                if (stack.peek() == 1) {
                    stack.pop();
                } else {
                    stack.push(stack.pop() - 1);
                }
            } else {
                //当遇到非空节点时,将栈顶元素减 1 后,再向栈中压入一个 2
                if (stack.peek() == 1) {
                    stack.pop();
                } else {
                    stack.push(stack.pop() - 1);
                }
                stack.push(2);
            }
        }

        return stack.isEmpty();
    }
}
